package leetcode; /**
 * description:
 * author:张腾
 * date:2021-06-18
 */

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回[-1, -1]
 */
public class leetcode34 {
    public int[] searchRange(int[] nums, int target) {
        int leftIndex = binarySearch(nums,target,true);
        int rightIndex = binarySearch(nums,target,false)-1;

        if (leftIndex<=rightIndex && rightIndex<=nums.length-1 && nums[leftIndex]==target&&nums[rightIndex]==target){
            return new int[]{leftIndex,rightIndex};
        }
        return new int[]{-1,-1};
    }

    //lower为true找数组中第一个>=target的下标；false找第一个>target的下标，-1即为最后一位=target的下标
    public int binarySearch(int[] nums,int target,boolean lower){
        int l = 0;
        int r = nums.length-1;
        int ans = nums.length-1;
        while (l<=r){
            int mid = l+(r-l)/2;
            if (nums[mid]>target || lower&&nums[mid]>=target){
                r = mid-1;
                ans = mid;
            }
            else l = mid+1;
        }
        return ans;
    }
}
